// 删除排序链表中的重复元素 II

package Leetcode;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class solution_082 {
    public ListNode deleteDuplicates(ListNode head) {
        // System.out.println(head.val);
        ListNode pre = new ListNode(); // 最终返回的结果，没有特殊意义
        ListNode slow = new ListNode(); // 纳入结果的结点
        ListNode fast = new ListNode(); // 目前遍历的结点
        slow.next = head; // slow一开始为空
        pre = slow;
        fast = head;// fast从head开始遍历
        while (fast != null) {
            // 如果fast和fast.next的值是不相等的，前者一定在结果里
            if (fast.next == null || fast.val != fast.next.val) {
                slow.next = fast;
                slow = slow.next;
                fast = fast.next;
            }
            // 相等则寻找与目前fast值不等的点
            else {
                ListNode index = fast.next.next;
                while (index != null) {
                    if (index.val != fast.val)
                        break;
                    index = index.next;
                }
                fast = index;
                // 如果fast为空那么while循环不再执行，但是slow依然有所指，所以进行赋值。
                if (fast == null)
                    slow.next = fast;
            }
        }
        return pre.next;
    }

    public static void main(String[] args) {
        solution_082 s = new solution_082();
        ListNode head = new ListNode(3);
        ListNode node1 = new ListNode(4);
        ListNode node2 = new ListNode(5);
        ListNode node3 = new ListNode(6);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        s.deleteDuplicates(head);
    }
}

public class Solution082 {

}
